import java.util.HashMap;
import java.util.Map;

/**
 * 318. 最大单词长度乘积
 */
public class No318 {
    /**
     * 1. 位运算预处理
     */
    public int maxProduct1(String[] words) {
        int ans = 0;
        int n = words.length;

        int[] mask = new int[n];
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray()) {
                mask[i] |= 1 << (c - 'a');
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int multi = words[i].length() * words[j].length();
                if (multi > ans && (mask[i] & mask[j]) == 0) ans = multi;
            }
        }
        return ans;
    }

    /**
     * 2. 哈希表优化
     */
    public int maxProduct2(String[] words) {
        int ans = 0;

        Map<Integer, Integer> map = new HashMap<>();
        for (String word : words) {
            int mask = 0;
            for (char c : word.toCharArray()) {
                mask |= 1 << (c - 'a');
            }
            if (!map.containsKey(mask) || word.length() > map.get(mask)) map.put(mask, word.length());
        }

        for (int k1 : map.keySet()) {
            for (int k2 : map.keySet()) {
                if ((k1 & k2) == 0) ans = Math.max(map.get(k1) * map.get(k2), ans);
            }
        }
        return ans;
    }
}
